class Solution {
public:
    int longestCommonSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        vector<vector<int>> memo(n, vector<int>(m, -1)); 
        auto dfs = [&](auto&& dfs, int i, int j) -> int 
        {
            if (i < 0 || j < 0) return 0;
            int &res = memo[i][j]; 
            if (res != -1) return res; 
            if (s[i] == t[j]) return res = dfs(dfs, i - 1, j - 1) + 1;
            return res = max(dfs(dfs, i - 1, j), dfs(dfs, i, j - 1));
        };
        return dfs(dfs, n - 1, m - 1);
    }
};

